/*!
 Temelia - Sorting algorithms interface.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef SORT_H_
#define SORT_H_

#include "platform.h"
#include "common.h"
#include "queue.h"

/*!
 * @brief Finds if a collection is sorted.
 * Complexity O(n)
 *
 * @param Collection
 * @param Size.
 * @param Pointer to index function.
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC int is_sorted(void *data, int size, void *(*key_at)(void *data, int index),
		int (*compare)(void *x, void *y, void *context), void *context);

/*!
 * @brief Bubble sort.
 * Complexity O(n*n)
 *
 * @param Pointer to collection
 * @param Size
 * @param Pointer to index function
 * @param Pointer to set function
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC void bubble_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Insertion sort.
 * Complexity O(n*n)
 *
 * @see bubble_sort
 */
DECLSPEC void insertion_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Merge sort.
 * Complexity O(n*log(n))
 *
 * @see bubble_sort
 */
DECLSPEC void merge_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Randomized quick sort.
 * Complexity O(n*log(n))
 *
 * @see bubble_sort
 */
DECLSPEC void quick_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Selection sort.
 * Complexity O(n*n)
 *
 * @see bubble_sort
 */
DECLSPEC void selection_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Shell sort.
 * Complexity O(n*log(n))
 *
 * @see bubble_sort
 */
DECLSPEC void shell_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Heap sort.
 * Complexity O(n*log(n))
 *
 * @see bubble_sort
 */
DECLSPEC void heap_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Gnome sort.
 * Complexity O(n*n)
 *
 * @see bubble_sort
 */
DECLSPEC void gnome_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Cocktail sort.
 * Complexity O(n*n)
 *
 * @see bubble_sort
 */
DECLSPEC void cocktail_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context);

/*!
 * @brief Radix sort.
 * Complexity O(ndigits * n) ~ O(n)
 * @param Array of integers
 * @param Size
 * @param Maximum digits number
 */
DECLSPEC void radix_sort(int *data, int size, int max_digits);

/*!
 * @brief Number sort. Values should be >= 0 and < size.
 * Complexity O(n)
 *
 * @param Array of integers
 * @param Size
 * @param Max value
 */
DECLSPEC void number_sort(unsigned int *data, int size, int max_value);

#endif /* SORT_H_ */
